package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/11 8:47
 * @description :7道
 * 力扣刷题不间断一个月了，刷题数到达200（其中有27道sql题），算是一个节点，继续走吧，春招，春招，春招。小米，拼多多，腾讯随便一个都好，冲
 * persevere to last
 * 2021.11.11
 * 李红磊
 * 2021年11月11日21:05:57
 */
public class t20211111 {


    //201.数字范围按位与
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }

        return right << shift;
    }

    //18.四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 4) return res;
        int len = nums.length;
        Arrays.sort(nums);//O(nlogn)


        for (int i = 0; i < len - 3; i++) {
            if (i > 0 && nums[i - 1] == nums[i]) continue;

            for (int j = i + 1; j < len - 2; j++) {
                if (j > i + 1 && nums[j - 1] == nums[j]) continue;

                int left = j + 1, right = len - 1;

                while (left < right) {
                    long temp = nums[i] + nums[j] + nums[left] + nums[right];
                    if (temp == target) {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        res.add(list);
                        while (left + 1 < right && nums[left] == nums[left + 1]) left++;
                        while (right - 1 > left && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (temp < target) {
                        left++;
                    } else {
                        right--;
                    }
                }


            }

        }

        return res;
    }

    //509.斐波那契数
    public int fib(int n) {
        if (n == 0) return 0;

        int first = 0, second = 1;

        for (int i = 2; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;

        }

        return second;
    }

    public int fib2(int n) {
        if (n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    //70.爬楼梯
    public int climbStairs(int n) {
        if (n == 1) return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public int climbStairs2(int n) {
        if (n == 1) return 1;
        int first = 1, second = 2;

        for (int i = 3; i < n + 1; i++) {
            int third = first + second;
            first = second;
            second = third;
        }

        return second;
    }

    //53.最大子序和
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) return nums[0];
        int cur = nums[0], res = cur, len = nums.length;

        for (int i = 1; i < len; i++) {
            if (cur > 0) {
                cur += nums[i];
            } else {
                cur = nums[i];
            }
            res = Math.max(res, cur);

        }
        return res;
    }

    public int maxSubArray2(int[] nums) {
        if (nums.length == 1) return nums[0];
        int len = nums.length, res = nums[0];
        int[] dp = new int[len + 1];
        dp[1] = nums[0];

        for (int i = 2; i <= len; i++) {
            dp[i] = Math.max(nums[i - 1], nums[i - 1] + dp[i - 1]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    //416.分隔等和子集
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 1) return false;

        //如果数组所有元素的和为奇数，则不会存在“从数组中挑一些正整数，使得它们的和等于整个数组元素和的一半”
        int sum = 0;
        for (int item : nums) {
            sum += item;
        }
        if ((sum & 1) == 1) return false;
        int target = sum / 2;
        boolean[][] dp = new boolean[len][target + 1];
/*
    dp[i][j]:表示能否从数组[0,i]中选取几个正整数，使得它们的和凑够j
*/
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        for (int i = 1; i < len; i++) {

            for (int j = 0; j <= target; j++) {
                //先写上，之后再做修改
                dp[i][j] = dp[i - 1][j];

                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }

                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }


            }


        }

        return dp[len - 1][target];
    }

    //20.有效的括号
    public boolean isValid(String s) {

        return false;
    }

    //496.下一个更大元素
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if (nums2.length == 1) return new int[]{-1};

        HashMap<Integer, Integer> map = new HashMap<>();

        ArrayDeque<Integer> stack = new ArrayDeque<>();

        //记录nums2中的位置关系
        for (int i = 0; i < nums2.length; i++) {

            while (!stack.isEmpty() && stack.peek() < nums2[i]) {
                int temp = stack.pop();
                map.put(temp, nums2[i]);
            }

            stack.offer(nums2[i]);

        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }

        return res;
    }

    //132.模式
    public boolean find132pattern(int[] nums) {
        if (nums == null || nums.length < 3) return false;
        int len = nums.length;

        ArrayDeque<Integer> stack = new ArrayDeque<>();

        int min = Integer.MIN_VALUE;

        for (int i = len - 1; i >= 0; i--) {
            if (nums[i] < min) return true;

            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                min = stack.pop();
            }
            stack.push(nums[i]);
        }

        return false;
    }


    //119.杨辉三角
    public List<Integer> getRow(int rowIndex) {
        ArrayList<Integer> pre = new ArrayList<>();
        ArrayList<Integer> cur = new ArrayList<>();

        for (int i = 0; i <= rowIndex; i++) {
            cur = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return pre;
    }

    //279.完全平方数
    public int numSquares(int n) {
        if (n == 1) return 1;
        //先找到所有可能用到的完全平方数
        int t = 1;
        ArrayList<Integer> list = new ArrayList<>();
        while (t * t <= n) {
            list.add(t * t);
            t++;
        }
        int size = list.size();
        int INF = 0X3f3f3f3f;

    /*                  包括i
        dp[i][j]:表示用list的前i个元素（这里面的元素都是完全平方数）去凑成j的最小个数
     */
        int[][] dp = new int[size + 1][n + 1];

        Arrays.fill(dp[0], INF);//假如用前0个元素，凑成不了任何数（除了0
        dp[0][0] = 0;

        for (int i = 1; i <= size; i++) {
            int x = list.get(i - 1);

            for (int j = 0; j <= n; j++) {
                // 对于不选第 i 个数的情况
                dp[i][j] = dp[i - 1][j];

                //对于选第 i 个数的情况
                for (int k = 1; k * x <= j; k++) {
                    // 能够选择 k 个 x 的前提是剩余的数字 j - k * x 也能被凑出
                    if (dp[i - 1][j - k * x] != INF) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * x] + k);
                    }
                }

            }

        }

        return dp[size][n];
    }

    private boolean judge(int num) {//判断是否为一个完全平方数
        int k = 1;
        while (num > 0) {
            num -= k;
            k += 2;
        }
        return num == 0;
    }

    private void test(int[] arr) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        ArrayDeque<Integer> assist = new ArrayDeque<>();

        for (int i = 0; i < arr.length; i++) {
            if (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.push(arr[i]);
                continue;
            } else if (!stack.isEmpty() && stack.peek() > arr[i]) {
                while (!stack.isEmpty()) {
                    assist.push(stack.pop());
                }
                stack.push(arr[i]);
                while (!assist.isEmpty()) {
                    stack.push(assist.poll());
                }
                continue;
            }
            stack.push(arr[i]);
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.poll() + "\t");
        }

    }

    public static void main(String[] args) {
        t20211111 t20211111 = new t20211111();
        System.out.println(t20211111.numSquares(3));

    }


}
